#ifndef __GGEAR_STRING_H
#define __GGEAR_STRING_H

#include "ggear_allocator.h"
#include "ggear_types.h"
#include "ggear_list.h"
#include "ggear_math.h"

namespace ggear
{
	namespace glb
	{
		class String
		{
		public:
			//! Default constructor
			String() : 
				mChars(null), mUsed(0), mCapacity(0)
			{
				  Reallocate(1);
				  drefs(mChars) = '\0';
				  mUsed = 1;
			}


			//! Construct new string from existing string
			String(const String& _str) :
				mChars(null), mUsed(0), mCapacity(0)
			{
				drefs(this) = _str;
			}

			
			//! Construct new string from character array
			template<class _Tx>
			String(const _Tx* const _arr) :
				mChars(null), mUsed(0), mCapacity(0)
			{
				drefs(this) = _arr;
			}

				
			//! Default destructor
			~String()
			{
				Clear();
			}


			//! Get the length of the string
			/** \return Number of characters contained in the string's contents. 
						Excluding the last null-terminated char.
			*/   
			u32 Length() const
			{
				return mUsed - 1;
			}


			//! Get size of allocated storage
			/** \return Size of allocated storage to hold string's content */
			u32 Capacity() const
			{
				return mCapacity;
			}


			//! Get string's content in C string format
			/** \return 16bits-char array presented as the string's content */
			const c16* Chars() const
			{
				return mChars;
			}


			//! Delete string's content
			void Clear()
			{
				if(!isnull(mChars))
				{
					mAlloc.Deallocate(mChars);
					mCapacity = mUsed = 0;
					mChars = null;
				}
			}


			//! Attach part of another string started at specified position and length to current string
			String& Append(const String& _str, u32 _strPos = 0, u32 _strNum = -1)
			{
				return Insert(Length(), _str.mChars, _str.Length(), _strPos, _strNum);
			}
			

			//! Attach part of content of character array started at specified position with specified length to current string
			template<class _Tx>
			String& Append(const _Tx* const _arr, u32 _arrPos = 0, u32 _arrNum = -1)
			{
				return Insert(Length(), _arr, 0, _arrPos, _arrNum);
			}


			//! Insert content of specified string into current string at specified position
			String& Insert(u32 _pos, const String& _str, u32 _strPos = 0, u32 _strNum = -1)
			{
				return Insert(_pos, _str.mChars, _str.Length(), _strPos, _strNum);
			}


			//! Insert content of character array into current string at specified position
			template<class _Tx>
			String& Insert(u32 _pos, const _Tx* const _arr, u32 _arrPos = 0, u32 _arrNum = -1)
			{
				return Insert(_pos, _arr, 0, _arrPos, _arrNum);
			}


			//! Remove a specified content from current string
			String& Remove(const String& _str, u32 _strPos = 0, u32 _strNum = -1)
			{
				return Remove(0, Length(), _str.mChars, _str.Length(), _strPos, _strNum);
			}


			//! Remove a specified content from current string
			template<class _Tx>
			String& Remove(const _Tx* const _arr, u32 _arrPos = 0, u32 _arrNum = -1)
			{
				return Remove(0, Length(), _arr, 0, _arrPos, _arrNum);
			}


			//! Remove a part of current string
			String& Remove(u32 _pos, u32 _len)
			{
				if(_pos >= Length() || !_len)
					return *this;

				//get length of removed content
				u32 count = _len < (Length() - _pos) ? _len : (Length() - _pos);
				u32 movedLen = Length() - (_pos + count);
				c16* ptr = mChars + (_pos + count);
				c16* nptr = mChars + _pos;

				for(u32 i = 0; i < movedLen ; i++)
					drefs(nptr++) = drefs(ptr++);

				for(u32 i = 0; i < count; i++)
					drefs(nptr++) = '\0';

				mUsed -= count;
				return drefs(this);
			}


			//! Replace part of current by a new content
			String& Replace(u32 _pos, u32 _num, const String& _str)
			{
				if(!_str.Length() || _pos >= Length() || !_num)
					return drefs(this);
				Remove(_pos, _num);
				Insert(_pos, _str);
				return drefs(this);
			}

			template<class _Tx>
			String& Replace(u32 _pos, u32 _num, const _Tx* const _arr)
			{
				if(isnull(_arr) || !drefs(_arr) || _pos >= Length() || !_num)
					return drefs(this);
				Remove(_pos, _num);
				Insert(_pos, _arr);
				return drefs(this);
			}

			String& Replace(const String& _old,const String& _new)
			{
				if(!_old.Length() || !_new.Length() || !_old.Length() > Length())
					return *this;

				s32  delta = _new.Length() - _old.Length();
				u32* idxs = new u32[(u32)(Length() / _old.Length())];
				u32 count = 0;
				c16* ptr = mChars;
				while(ptr < mChars + Length())
				{
					u32 matched = 0;
					for(;drefs(ptr + matched) == drefs(_old.mChars + matched); matched++);
					if(matched == _old.Length())
					{
						idxs[count] = (ptr - mChars);
						count++;
					}
					ptr += Math::Max((u32)1, matched);
				}
				Reallocate(mUsed + delta * count, true);
				if(delta > 0)
				{
					ptr = mChars + Length() - 1;
					c16* nptr = mChars + Length() + delta * count - 1;
					drefs(nptr + 1) = '\0';
					while(count)
					{ 
						drefs(nptr--) = drefs(ptr--);
						u32 idx = (ptr - mChars) - _old.Length() + 1;
						if(idx == idxs[count - 1])
						{
 							for(u32 i = _new.Length(); i > 0; i--)
 								drefs(nptr--) = drefs(_new.mChars + i - 1); 
							ptr -= _old.Length();
							count--;
						}
					}
				}
				else
				{
					u32 k = 0;
					ptr = mChars + idxs[k];
					c16* nptr = mChars + idxs[k];
					while(count > k || (ptr - mChars) < Length())
					{
						if(ptr - mChars == idxs[k])
						{
							for(u32 i = 0; i < _new.Length(); i++)
								drefs(nptr++) = drefs(_new.mChars + i);
							ptr += _old.Length();
							k++;
						}
						drefs(nptr++) = drefs(ptr++);
					}
					drefs(nptr) = '\0';
				}
				mUsed += delta * count;
				delete [] idxs;
				return *this;
			}

			//! Get the substring from current string
			/** \param _pos Position where to start get substring
				\param _len Number of chars in substring
				\return		Substring that start at _pos position with _len length . 
							Otherwise return empty if failed.
			*/
			String SubStr(u32 _pos, u32 _num = -1) const
			{
				if(_pos >= Length() || !_num)
					return String();
				
				u32 count = _num < (Length() - _pos) ? _num : (Length() - _pos);
				c16 tmp = drefs(mChars + _pos + count);
				drefs(mChars + _pos + count) = '\0';
				String res (mChars + _pos);
				drefs(mChars + _pos + count) = tmp;
				return res;
			}


			//! Get copy of the string converted to lower case
			String ToLower() const
			{
				String ret(*this);
				for(u32 i = 0; i < ret.Length(); i++)
					drefs(ret.mChars + i) = localeLower(drefs(ret.mChars + i));
				return ret;
			}


			//! Get copy of the string converted to upper case
			String ToUpper() const
			{
				String ret(*this);
				for(u32 i = 0; i < ret.Length(); i++)
				{
					c16 c = drefs(ret.mChars + i);
					if(c > 0x60 && c < 0x7B) // a ... z
						drefs(ret.mChars + i) -= 0x20;

				}
				return ret;
			}

			b8 Equal(const String& _str, b8 _ignoreCase = false) const
			{
				if(_str.mUsed != mUsed) 
					return false;

				for(u32 i = 0; i < mUsed; i++)
					if(_str.mChars[i] != mChars[i])
						if(!_ignoreCase ? true : localeLower(_str.mChars[i]) == localeLower(mChars[i])) 
							return false;
				return true;
			}

			//! Find the first occurrence of specified content inside the string
			/** \param _str Content to search
				\param _pos	Position where to start searching . Default is 0 (from beginning)
				\param _num Number of chars to search
				\return		Position of first occurrence of _str or -1 if not found.
			*/
			u32 IndexOf(const String& _str, u32 _pos = 0, u32 _num = -1) const
			{
				if(_pos >= _str.Length() || !_num)
					return -1;

				u32 count = _num < (_str.Length() - _pos) ? _num : (_str.Length() - _pos);

				c16* ptr = mChars;
				c16* aptr = _str.mChars + _pos;
				while(ptr < mChars + Length())
				{
					u32 matched = 0;
					for(;drefs(ptr + matched) == drefs(aptr + matched)
						&& matched < count;
						matched++);
					
					if(matched == count)
						return ptr - mChars;
					
					ptr += !matched  ? 1 : matched; 
				}

				return -1;
			}


			template<class _Tx>
			u32 IndexOf(const _Tx* const _arr, u32 _pos = 0, u32 _num = -1) const
			{
				if(!_arr ? true : (!drefs(_arr) || !drefs(_arr + _pos) || !_num)) 
					return -1;

				c16* ptr = mChars;
				c16* aptr = _arr + _pos;
				while(ptr < mChars + Length())
				{
					u32 matched = 0;
					for(;drefs(ptr + matched) == drefs(aptr + matched)
						&& !drefs(aptr + matched)
						&& matched < _num; 
						matched++);

					if(!drefs(aptr + matched) || matched == _num)
						return (ptr - mChars);
					
					ptr += !matched ? 1 : matched;
				}

				return -1;
			}
			

			//! Find the last occurrence of specified content inside the string
			/** \param _str Content to search
				\param _pos	Position where to start searching . Default is 0 (from beginning)
				\param _num Number of chars to search
				\return		Position of first occurrence of _str or -1 if not found.
			*/
			u32 LastIndexOf(const String& _str, u32 _pos = 0, u32 _num = -1) const
			{
				if(_pos >= _str.Length() || !_num)
					return -1;

				u32 count = _num < (_str.Length() - _pos) ? _num : (_str.Length() - _pos);

				c16* ptr = mChars + (mUsed - 2);
				c16* aptr = _str.mChars + (_str.mUsed - 2);
				while(ptr > mChars)
				{
					u32 matched = 0;
					for(;drefs(ptr - matched) == drefs(aptr - matched)
						&& matched < count;
						matched++);

					if(matched == count)
						return ptr - mChars;

					ptr -= !matched ? 1 : matched;
				}

				return -1;
			}

			
			template<class _Tx>
			u32 LastIndexOf(const _Tx* const _arr, u32 _pos = 0, u32 _num = -1) const
			{
				if(!_arr ? true : (!drefs(_arr) || !drefs(_arr + _pos) || !_num)) 
					return -1;

				c16* ptr = mChars + (mUsed - 2);
				c16* aptr = _arr + _pos;
				while(ptr > mChars)
				{
					u32 matched = 0;
					for(;drefs(ptr + matched) == drefs(aptr + matched)
						&& !drefs(aptr + matched)
						&& matched < _num; 
					matched++);

					if(!drefs(aptr + matched) || matched == _num)
						return (ptr - mChars);

					ptr -= !matched ? 1 : matched;
				}

				return -1;
			}

			
			//! Split string into substring
			/** \param _subs	 Output container to hold resulted sub-strings
				\param _seps	 Input list of separators
				\param _remEmpty Remove all empty entries
				\param _keepSep	 Include separator in resulted substrings

				THIS MAYBE SLOW NEED TO BE OPTIMIZED
			*/
			u32 Split(List<String>* _subs, const List<String>* _seps, b8 _remEmpty = false, b8 _keepSep = false) const
			{
				if(!_subs || !_seps || !_seps->Count()) return 0;

				c16* los = mChars;
				c16* cos = mChars;
				c16* eos = mChars + Length();
				while(cos < eos)
				{
					u32 minMatched = 0;
					for(u32 i = 0; i < _seps->Count(); i++)
					{
						u32 sepLen = _seps->Get(i).Length();
						const c16* sepPtr = _seps->Get(i).Chars();
						u32 matched = 0;
						for(;drefs(cos + matched) == drefs(sepPtr + matched)
							&& matched < sepLen; matched++);
						
						if(matched == sepLen)
						{
							_subs->PushBack(SubStr(los - mChars, cos - los));
							los = cos + sepLen;
							minMatched = matched;
							break;
						}
						if(!i) minMatched = matched;
						else minMatched = Math::Min(minMatched, matched);
					}
					cos += !minMatched ? 1 : minMatched;
				}
				_subs->PushBack(SubStr(los - mChars, eos - los));
				return _subs->Count();
			}

		
			//! Copy content from another string
			String& operator = (const String& _str)
			{
				if(!_str.Length() || !drefs(_str.mChars))
				{
					if(!mChars)
						Reallocate(1);
					drefs(mChars) = '\0';
					mUsed = 1;
					return drefs(this);
				}

				Reallocate(_str.mUsed);
				for(mUsed = 0; mUsed < _str.mUsed; mUsed++)
					drefs(mChars + mUsed) = drefs(_str.mChars + mUsed);

				return drefs(this);
			}


			//! Copy content from character array into the string
			template<class _Tx>
			String& operator = (const _Tx* const _arr)
			{
				if(isnull(_arr) ? true : !drefs(_arr))
				{
					if(!mChars)
						Reallocate(1);
					drefs(mChars) = '\0';
					mUsed = 1;
					return drefs(this);
				}

				// count number of characters in _arr
				u32 count = 0;
				for(;drefs(_arr + count) != 0; count++);

				Reallocate(count + 1);
				for(mUsed = 0; mUsed <= count; mUsed++)
					drefs(mChars + mUsed) = drefs(_arr + mUsed);
		
				return drefs(this);
			}


			//! Attach another string to current string
			String& operator += (const String& _str)
			{
				return Append(_str);
			}


			//! Attach character array to current string
			template<class _Tx>
			String& operator += (const _Tx* const _arr)
			{
				return Append(_arr);
			}


			//! Array access operator: get or set character at specified position in string
			c16& operator [] (u32 _pos)
			{
				if(_pos > Length()) throw "Exception";
				return mChars[_pos];
			}

			c16 operator [] (u32 _pos) const
			{
				if(_pos > Length()) throw "Exception";
				return mChars[_pos];
			}


			//! Check whether two strings have the same content or not
			friend bool operator == (const String& _lst, const String& _rst)
			{
				if(_lst.mUsed != _rst.mUsed)
					return false;

				return (_lst == _rst.mChars);
			}

			//! Check if current string has the same content as w-char array
			template<class _Tx>
			friend bool operator == (const String& _lst, const _Tx* const _arr)
			{
				if(isnull(_arr))
					return false;

				if(drefs(_lst.mChars + _lst.Length()) != drefs(_arr + _lst.Length()))
					return false;

				for(u32 i = 0; i < _lst.Length(); i++)
					if(drefs(_lst.mChars + i) != drefs(_arr + i))
						return false;

				return true;
			}


			//! Check if two strings have different content
			friend bool operator != (const String& _lst, const String _rst)
			{
				return !(_lst == _rst);
			}

			//! Check if current string has different content with the content of character array
			template<class _Tx>
			friend bool operator != (const String& _lst, const _Tx* const _arr)
			{
				return !(_lst == _arr);
			}


			//! Concatenate two string together
			friend String operator + (const String& _lst, const String& _rst)
			{
				return (String(_lst)).Append(_rst);
			}


			//! Attach content of character array to an existing string
			template<class _Tx>
			friend String operator + (const String& _lst, const _Tx* const _arr)
			{
				return (String(_lst)).Append(_arr);
			}

		private:
			//! Allocate block of memory with desired size
			/** \param _size	The requested size of storage to hold string's content.
				\param _keepOld Set this to TRUE to keep old content during the allocation.
				\param _forced	Set this to TRUE to force do the allocation . Otherwise allocation 
								can only be done if requested size is bigger.
			*/
			void Reallocate(u32 _size, b8 _keepOld = false, b8 _forced = false)
			{
				if(_size <= mCapacity && !_forced) 
					return; // no need to allocate new memory block

				c16* buffer = mAlloc.Allocate(_size);

				if(isnull(buffer)) throw "OutOfMem"; //error occurred

				// copy old content for later uses
				u32 used = 0;
				while(used < mUsed && used < _size && !isnull(mChars) && _keepOld) 
				{
					drefs(buffer + used) = drefs(mChars + used);
					used++;
				}

				mAlloc.Deallocate(mChars);
				mChars = buffer;
				mCapacity = _size;
				mUsed = used;
			}

			//! Insert new content into current string
			template<class _Tx>
			String& Insert(u32 _pos, const _Tx* const _arr, 
						   u32 _arrLen , u32 _arrPos, u32 _arrNum)
			{
				if(isnull(_arr) ? true : !drefs(_arr) || !drefs(_arr + _arrPos) || !_arrNum || _pos > Length())
					return *this; //there is no string to insert

				// count number of characters in _arr if needed
				u32 arrLen = _arrLen;
				for(;!_arrLen && drefs(_arr + arrLen); arrLen++);

				if(_arrPos >= arrLen) return *this;

				//get length of inserted content
				u32 count = _arrNum < (arrLen - _arrPos)? _arrNum : (arrLen - _arrPos);

				//allocate new storage if needed 
				Reallocate(mUsed + count, true);

				c16* ptr = mChars + (mUsed - 2);
				c16* nptr = mChars + (mUsed + count - 2);
				const _Tx* aptr = _arr + (_arrPos + count - 1);

				for(u32 movedLen = Length() - _pos; movedLen > 0; movedLen--)
					drefs(nptr--) = drefs(ptr--);

				for(u32 insertedLen = count; insertedLen > 0; insertedLen--)
					drefs(nptr--) = drefs(aptr--); 

				mUsed += count;
				drefs(mChars + Length()) = '\0';
				return *this;
			}

			//! Remove part of content from this string
			template<class _Tx>
			String& Remove(u32 _pos, u32 _num, const _Tx* const _arr, 
						   u32 _arrLen, u32 _arrPos, u32 _arrNum)
			{
				if((isnull(_arr) ? true : !drefs(_arr) || !drefs(_arr + _arrPos)) 
					|| !_arrNum	|| _pos >= Length() || !_num)
					return *this;

				// count number of characters in _arr if needed
				u32 arrLen = _arrLen;
				for(;!_arrLen && !drefs(_arr + arrLen); arrLen++);

				if(_arrPos >= arrLen) return *this;

				//max number of chars need to compare 
				u32 limit = _num < (Length() - _pos) ? _num : (Length() - _pos);

				//get length of compared string
				u32 count = _arrNum < (arrLen - _arrPos) ? _arrNum : (arrLen - _arrPos);
				
				if(limit < count) return *this;

				c16* ptr = mChars + _pos;
				c16* end = mChars + _pos + limit;
				const _Tx* aptr = _arr + _arrPos;
				while(ptr < end)
				{
					u32 matched = 0;
					for(;(drefs(aptr + matched) == drefs(ptr + matched)) && 
						(matched < count); matched++);

						if(matched == count)
						{
							Remove(ptr - mChars, count);
							continue;
						}

						ptr += !matched ? 1 : matched;
				}
				return drefs(this);
			}

			//! WILL SUPPORT MORE LANGUAGE
			c16 localeLower(c16 _chr) const
			{
				//for ASCII and ANSI lowering
				if(_chr > 0x40 && _chr < 0x5B) // A ... Z
					return _chr + 0x20;
				return _chr;
			}
		private:
			c16* mChars;
			u32 mUsed;
			u32 mCapacity;
			Allocator<c16> mAlloc;
		};
	}
}
#endif